:- module(tp2, [distHam/3, distPref/3, distEd/3]).

%------------------------------------------------
%              Predicados Auxiliares
%------------------------------------------------

% Solo vamos a trabajar con cadenas de 0's y 1's
elemValido(0).
elemValido(1).

% Esto valida que D sea una variable que pueda unificar con un numero
distanciaNoInstanciada(D) :- var(D), not(not(D is 0)).

% Determina los Z que estan entre X e Y inclusive
entre(X, Y, X) :- X =< Y.
entre(X, Y, Z) :- X < Y, N is X+1, entre(N, Y, Z).

% Determina/genera una cadena compuesta por elementos validos
cadenaValidaDeLong([], 0).
cadenaValidaDeLong([X|Xs], N) :-
    ground(N), N>0, M is N-1,
    elemValido(X), cadenaValidaDeLong(Xs, M).
cadenaValidaDeLong([X|Xs], N) :-
    not(ground(N)), ground(X),
    elemValido(X), cadenaValidaDeLong(Xs, M), N is M+1.
cadenaValidaDeLong([X|Xs], N) :-
    not(ground(N)), not(ground(X)),
    cadenaValidaDeLong(Xs, M), elemValido(X), N is M+1.

%------------------------------------------------
%              Distancia de Hamming
%------------------------------------------------
distHam([], [], 0).
distHam([X|Xs], [X|Ys], N) :- elemValido(X), distHam(Xs, Ys, N).
distHam([X|Xs], [Y|Ys], N) :- elemValido(X), elemValido(Y), X \= Y, distHam(Xs, Ys, NAnt), N is NAnt + 1.


%------------------------------------------------
%              Distancia de Prefijos
%------------------------------------------------

% Dadas 2 cadenas, encuentra el prefijo comun mas largo entre ellas
prefijoComunMasLargo([], [], []).
prefijoComunMasLargo([_|Xs], [], []) :- prefijoComunMasLargo(Xs, [], []).
prefijoComunMasLargo([], [_|Xs], []) :- prefijoComunMasLargo([], Xs, []).
prefijoComunMasLargo([X|_], [Y|_], []) :- X \= Y.
prefijoComunMasLargo([X|Xs], [X|Ys], [X|Zs]) :- prefijoComunMasLargo(Xs, Ys, Zs).

% distPref(+L1, ?L2, ?L3)
distPref(X, Y, N) :- integer(N), N >=0,
	cadenaValidaDeLong(X,Nx),
	Nmax is Nx + N,
	entre(0, Nmax, Ny),
	cadenaValidaDeLong(Y, Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).
distPref(X, Y, N) :- var(N),
	cadenaValidaDeLong(X, Nx),
	cadenaValidaDeLong(Y, Ny),
	prefijoComunMasLargo(X, Y, Z), 
	cadenaValidaDeLong(Z, Nz), 
	N is (Nx - Nz) + (Ny - Nz).


%------------------------------------------------
%              Distancia de Edicion
%------------------------------------------------

% distEd(+L1, ?L2, ?D)
distEd(L1, L2, D) :-
    integer(D), D >=0,
    % Verificar que L1 tiene elementos validos
    cadenaValidaDeLong(L1, L1N),
    % La longitud de la segunda lista esta acotada superiormente por la longitud
    % de la primera mas la cantidad de operaciones de la distancia de edicion    
    L2Max is L1N+D,
    entre(0, L2Max, L2N), 
    % Si L2 no viene instanciada, instanciarla con elementos validos. Si viene
    % instanciada, chequear que tenga elementos validos. 
    cadenaValidaDeLong(L2, L2N),
    llegoEnDPasos(L1, L2, D).    
distEd(L1, L2, D) :-
    var(D),
    % Chequear elementos validos en L1
    cadenaValidaDeLong(L1, L1N),
    % Instanciar L2 y/o chequear que tiene elementos validos
    cadenaValidaDeLong(L2, L2N),
    LMax is max(L1N, L2N),
    % La cantidad de operaciones esta acotada superiormente por la longitud
    % de la lista mas larga
    entre(0, LMax, D),
    llegoEnDPasos(L1, L2, D).

% llegoEnDPasos(+L1, +L2, +D) devuelve la distancia de edicion
llegoEnDPasos([], [], 0).
llegoEnDPasos([X|Xs], [X|Ys], D) :- llegoEnDPasos(Xs, Ys, D).
llegoEnDPasos(Xs, Ys, D) :-
    % El caso de 2 listas vacias ya lo cubrimos con llegoEnDPasos([], [], 0)
    not(append(Xs, Ys, [])),
    % El caso de un prefijo en comun no vacio lo cubrimos
    % con llegoEnDPasos([X|Xs], [X|Ys], D)
    prefijoComunMasLargo(Xs, Ys, []),
    % Nos quedamos con las posibles distancias de edicion empezando con
    % distintas operaciones basicas
    findall(A, aplico(_, Xs, Ys, A), Ds),
    % La distancia de edicion es la minima entre las distintas alternativas que cumplen
    min_list(Ds, D).

% Las operaciones basicas siempre van a ser llamadas con listas donde al menos
% una es no vacia, y ademas las listas no van a tener un prefijo comun entre si.
% Esto asegura que al menos uno de los siguientes predicados va a unificar con
% los argumentos y devolver una distancia de edicion.
aplico(modificacion, [X|Xs], [Y|Ys], M) :- Y \= X, llegoEnDPasos(Xs, Ys, D), M is D+1.
aplico(eliminacion, [_|Xs], Ys, E) :- llegoEnDPasos(Xs, Ys, D), E is D+1.
aplico(insercion, Xs, [_|Ys], I) :- llegoEnDPasos(Xs, Ys, D), I is D+1.

